home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / pcutils / os2 / rt / shape.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-31  |  31.8 KB  |  1,430 lines
  1. /*
  2.  
  3. SHAPE.C  General shapes
  4.  
  5. */
  6.  
  7. /*...sincludes:0:*/
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <stddef.h>
  11. #include <malloc.h>
  12. #include <memory.h>
  13. #include <math.h>
  14. #include "standard.h"
  15. #include "rt.h"
  16. #include "fio.h"
  17. #include "tex.h"
  18. #include "vector.h"
  19. #include "rgbvec.h"
  20. #include "col.h"
  21. #include "surf.h"
  22. #include "sil.h"
  23. #include "plane.h"
  24. #include "biplane.h"
  25. #include "sphere.h"
  26. #include "quad.h"
  27. #define    _SHAPE_
  28. #include "shape.h"
  29.  
  30. /*...vrt\46\h:0:*/
  31. /*...vfio\46\h:0:*/
  32. /*...vtex\46\h:0:*/
  33. /*...vvector\46\h:0:*/
  34. /*...vrgbvec\46\h:0:*/
  35. /*...vcol\46\h:0:*/
  36. /*...vsurf\46\h:0:*/
  37. /*...vsil\46\h:0:*/
  38. /*...vplane\46\h:0:*/
  39. /*...vbiplane\46\h:0:*/
  40. /*...vsphere\46\h:0:*/
  41. /*...vquad\46\h:0:*/
  42. /*...vshape\46\h:0:*/
  43. /*...e*/
  44.  
  45. /*...screate_plane_shape   \45\ create a shape tree consisting of a single plane:0:*/
  46. SHAPE    *create_plane_shape(PLANE *plane, SURF *surf)
  47.     {
  48.     SHAPE    *shape;
  49.  
  50.     if ( (shape = malloc(sizeof(SHAPE))) == NULL )
  51.         return NULL;
  52.  
  53.     shape->stype   = STYPE_PLANE;
  54.     shape->u.plane = plane;
  55.     shape->surf    = surf;
  56.     return shape;
  57.     }
  58. /*...e*/
  59. /*...screate_biplane_shape \45\ create a shape tree consisting of a single plane:0:*/
  60. SHAPE    *create_biplane_shape(BIPLANE *biplane, SURF *surf)
  61.     {
  62.     SHAPE    *shape;
  63.  
  64.     if ( (shape = malloc(sizeof(SHAPE))) == NULL )
  65.         return NULL;
  66.  
  67.     shape->stype     = STYPE_BIPLANE;
  68.     shape->u.biplane = biplane;
  69.     shape->surf      = surf;
  70.     return shape;
  71.     }
  72. /*...e*/
  73. /*...screate_sphere_shape  \45\ create a shape tree consisting of a single sphere:0:*/
  74. SHAPE    *create_sphere_shape(SPHERE *sphere, SURF *surf)
  75.     {
  76.     SHAPE    *shape;
  77.  
  78.     if ( (shape = malloc(sizeof(SHAPE))) == NULL )
  79.         return NULL;
  80.  
  81.     shape->stype    = STYPE_SPHERE;
  82.     shape->u.sphere = sphere;
  83.     shape->surf     = surf;
  84.     return shape;
  85.     }
  86. /*...e*/
  87. /*...screate_quad_shape    \45\ create a shape tree consisting of a single quadratic:0:*/
  88. SHAPE    *create_quad_shape(QUAD *quad, SURF *surf)
  89.     {
  90.     SHAPE    *shape;
  91.  
  92.     if ( (shape = malloc(sizeof(SHAPE))) == NULL )
  93.         return NULL;
  94.  
  95.     shape->stype  = STYPE_QUAD;
  96.     shape->u.quad = quad;
  97.     shape->surf   = surf;
  98.     return shape;
  99.     }
  100. /*...e*/
  101. /*...screate_bin_shape     \45\ create a binary shape tree made of 2 shapes:0:*/
  102. SHAPE    *create_bin_shape(STYPE stype, SHAPE *shape0, SHAPE *shape1)
  103.     {
  104.     SHAPE    *shape;
  105.  
  106.     if ( (shape = malloc(sizeof(SHAPE))) == NULL )
  107.         return NULL;
  108.  
  109.     shape->stype       = stype;
  110.     shape->u.shapes[0] = shape0;
  111.     shape->u.shapes[1] = shape1;
  112.     return shape;
  113.     }
  114. /*...e*/
  115. /*...scopy_shape           \45\ make a complete copy of a shape tree:0:*/
  116. SHAPE    *copy_shape(SHAPE *shape)
  117.     {
  118.     SHAPE    *copy;
  119.  
  120.     if ( (copy = malloc(sizeof(SHAPE))) == NULL )
  121.         return NULL;
  122.  
  123.     copy->stype = shape->stype;
  124.  
  125.     if ( shape->stype <= STYPE_QUAD )
  126.         /* Leaf node */
  127.         {
  128.         if ( (copy->surf = copy_surf(shape->surf)) == NULL )
  129.             {
  130.             free(copy);
  131.             return NULL;
  132.             }
  133.         switch ( shape->stype )
  134.             {
  135. /*...sSTYPE_PLANE:24:*/
  136. case STYPE_PLANE:
  137.     if ( (copy->u.plane = copy_plane(shape->u.plane)) == NULL )
  138.         {
  139.         destroy_surf(copy->surf);
  140.         free(copy);
  141.         return NULL;
  142.         }
  143.     break;
  144. /*...e*/
  145. /*...sSTYPE_BIPLANE:24:*/
  146. case STYPE_BIPLANE:
  147.     if ( (copy->u.biplane = copy_biplane(shape->u.biplane)) == NULL )
  148.         {
  149.         destroy_surf(copy->surf);
  150.         free(copy);
  151.         return NULL;
  152.         }
  153.     break;
  154. /*...e*/
  155. /*...sSTYPE_SPHERE:24:*/
  156. case STYPE_SPHERE:
  157.     if ( (copy->u.sphere = copy_sphere(shape->u.sphere)) == NULL )
  158.         {
  159.         destroy_surf(copy->surf);
  160.         free(copy);
  161.         return NULL;
  162.         }
  163.     break;
  164. /*...e*/
  165. /*...sSTYPE_QUAD:24:*/
  166. case STYPE_QUAD:
  167.     if ( (copy->u.quad = copy_quad(shape->u.quad)) == NULL )
  168.         {
  169.         destroy_surf(copy->surf);
  170.         free(copy);
  171.         return NULL;
  172.         }
  173.     break;
  174. /*...e*/
  175.             }
  176.         }
  177.     else
  178. /*...sboolean combinations:16:*/
  179. {
  180. if ( (copy->u.shapes[0] = copy_shape(shape->u.shapes[0])) == NULL )
  181.     {
  182.     free(copy);
  183.     return NULL;
  184.     }
  185. if ( (copy->u.shapes[1] = copy_shape(shape->u.shapes[1])) == NULL )
  186.     {
  187.     free(copy->u.shapes[0]);
  188.     free(copy);
  189.     return NULL;
  190.     }
  191. }
  192. /*...e*/
  193.  
  194.     return copy;
  195.     }
  196. /*...e*/
  197. /*...sdestroy_shape        \45\ delete a shape tree:0:*/
  198. void    destroy_shape(SHAPE *shape)
  199.     {
  200.     if ( shape->stype <= STYPE_QUAD )
  201.         /* Leaf node */
  202.         {
  203.         destroy_surf(shape->surf);
  204.         switch ( shape->stype )
  205.             {
  206. /*...sSTYPE_PLANE:24:*/
  207. case STYPE_PLANE:
  208.     destroy_plane(shape->u.plane);
  209.     break;
  210. /*...e*/
  211. /*...sSTYPE_BIPLANE:24:*/
  212. case STYPE_BIPLANE:
  213.     destroy_biplane(shape->u.biplane);
  214.     break;
  215. /*...e*/
  216. /*...sSTYPE_SPHERE:24:*/
  217. case STYPE_SPHERE:
  218.     destroy_sphere(shape->u.sphere);
  219.     break;
  220. /*...e*/
  221. /*...sSTYPE_QUAD:24:*/
  222. case STYPE_QUAD:
  223.     destroy_quad(shape->u.quad);
  224.     break;
  225. /*...e*/
  226.             }
  227.         }
  228.     else
  229.         {
  230.         destroy_shape(shape->u.shapes[0]);
  231.         destroy_shape(shape->u.shapes[1]);
  232.         }
  233.  
  234.     free(shape);
  235.     }
  236. /*...e*/
  237. /*...ssphere_to_quad       \45\ convert sphere to quad:0:*/
  238. /*
  239. Spheres cannot be rescaled in each direction and remain a sphere.
  240. Hence this code will convert a sphere into the equivelent quadratic.
  241.  
  242.                  2      2      2
  243.     Sphere:        (x-a) +(y-b) +(z-c) -d <=0
  244.  
  245.              2      2  2      2  2      2
  246.             x -2ax+a +y -2by+b +z -2cz+c -d <= 0
  247.  
  248.               2   2   2
  249.     Quadratic:    ax +by +cz +dxy+eyz+fzx+gx+hy+iz+j<=0
  250.  
  251. */
  252.  
  253. static BOOLEAN sphere_to_quad(SHAPE *shape)
  254.     {
  255.     SPHERE *sphere = shape->u.sphere;
  256.     QUAD *quad;
  257.  
  258.     if ( (quad = create_quad(1.0, 1.0, 1.0, 0.0, 0.0, 0.0,
  259.          -2.0 * sphere->a, -2.0 * sphere->b, -2.0 * sphere->c,
  260.          - sphere->d)) == NULL )
  261.         return FALSE;
  262.  
  263.     destroy_sphere(shape->u.sphere);
  264.     shape->stype = STYPE_QUAD;
  265.     shape->u.quad = quad;
  266.  
  267.     return TRUE;
  268.     }
  269. /*...e*/
  270.  
  271. /*...strans_x              \45\ translate by amount in x direction:0:*/
  272. void    trans_x(SHAPE *shape, double t)
  273.     {
  274.     if ( shape->stype <= STYPE_QUAD )
  275.         {
  276.         switch ( shape->stype )
  277.             {
  278.             case STYPE_PLANE:
  279.                 trans_x_plane(shape->u.plane, t);
  280.                 break;
  281.             case STYPE_BIPLANE:
  282.                 trans_x_biplane(shape->u.biplane, t);
  283.                 break;
  284.             case STYPE_SPHERE:
  285.                 trans_x_sphere(shape->u.sphere, t);
  286.                 break;
  287.             case STYPE_QUAD:
  288.                 trans_x_quad(shape->u.quad, t);
  289.                 break;
  290.             }
  291.         trans_x_surf(shape->surf, t);
  292.         }
  293.     else
  294.         {
  295.         trans_x(shape->u.shapes[0], t);
  296.         trans_x(shape->u.shapes[1], t);
  297.         }
  298.     }
  299. /*...e*/
  300. /*...strans_y              \45\ translate by amount in y direction:0:*/
  301. void    trans_y(SHAPE *shape, double t)
  302.     {
  303.     if ( shape->stype <= STYPE_QUAD )
  304.         {
  305.         switch ( shape->stype )
  306.             {
  307.             case STYPE_PLANE:
  308.                 trans_y_plane(shape->u.plane, t);
  309.                 break;
  310.             case STYPE_BIPLANE:
  311.                 trans_y_biplane(shape->u.biplane, t);
  312.                 break;
  313.             case STYPE_SPHERE:
  314.                 trans_y_sphere(shape->u.sphere, t);
  315.                 break;
  316.             case STYPE_QUAD:
  317.                 trans_y_quad(shape->u.quad, t);
  318.                 break;
  319.             }
  320.         trans_y_surf(shape->surf, t);
  321.         }
  322.     else
  323.         {
  324.         trans_y(shape->u.shapes[0], t);
  325.         trans_y(shape->u.shapes[1], t);
  326.         }
  327.     }
  328. /*...e*/
  329. /*...strans_z              \45\ translate by amount in z direction:0:*/
  330. void    trans_z(SHAPE *shape, double t)
  331.     {
  332.     if ( shape->stype <= STYPE_QUAD )
  333.         {
  334.         switch ( shape->stype )
  335.             {
  336.             case STYPE_PLANE:
  337.                 trans_z_plane(shape->u.plane, t);
  338.                 break;
  339.             case STYPE_BIPLANE:
  340.                 trans_z_biplane(shape->u.biplane, t);
  341.                 break;
  342.             case STYPE_SPHERE:
  343.                 trans_z_sphere(shape->u.sphere, t);
  344.                 break;
  345.             case STYPE_QUAD:
  346.                 trans_z_quad(shape->u.quad, t);
  347.                 break;
  348.             }
  349.         trans_z_surf(shape->surf, t);
  350.         }
  351.     else
  352.         {
  353.         trans_z(shape->u.shapes[0], t);
  354.         trans_z(shape->u.shapes[1], t);
  355.         }
  356.     }
  357. /*...e*/
  358. /*...strans                \45\ translate by vector:0:*/
  359. void    trans(SHAPE *shape, VECTOR v)
  360.     {
  361.     trans_x(shape, v.x);
  362.     trans_y(shape, v.y);
  363.     trans_z(shape, v.z);
  364.     }
  365. /*...e*/
  366. /*...sscale_x              \45\ scale by factor in x direction:0:*/
  367. BOOLEAN    scale_x(SHAPE *shape, double factor)
  368.     {
  369.     if ( factor == 1.0 )
  370.         return TRUE;
  371.  
  372.     if ( shape->stype <= STYPE_QUAD )
  373.         {
  374.         switch ( shape->stype )
  375.             {
  376.             case STYPE_PLANE:
  377.                 scale_x_plane(shape->u.plane, factor);
  378.                 break;
  379.             case STYPE_BIPLANE:
  380.                 scale_x_biplane(shape->u.biplane, factor);
  381.                 break;
  382.             case STYPE_SPHERE:
  383.                 if ( !sphere_to_quad(shape) )
  384.                     return FALSE;
  385.                 scale_x_quad(shape->u.quad, factor);
  386.                 break;
  387.             case STYPE_QUAD:
  388.                 scale_x_quad(shape->u.quad, factor);
  389.                 break;
  390.             }
  391.         scale_x_surf(shape->surf, factor);
  392.         }
  393.     else
  394.         {
  395.         if ( !scale_x(shape->u.shapes[0], factor) ||
  396.              !scale_x(shape->u.shapes[1], factor) )
  397.             return FALSE;
  398.         }
  399.     return TRUE;
  400.     }
  401. /*...e*/
  402. /*...sscale_y              \45\ scale by factor in y direction:0:*/
  403. BOOLEAN    scale_y(SHAPE *shape, double factor)
  404.     {
  405.     if ( factor == 1.0 )
  406.         return TRUE;
  407.  
  408.     if ( shape->stype <= STYPE_QUAD )
  409.         {
  410.         switch ( shape->stype )
  411.             {
  412.             case STYPE_PLANE:
  413.                 scale_y_plane(shape->u.plane, factor);
  414.                 break;
  415.             case STYPE_BIPLANE:
  416.                 scale_y_biplane(shape->u.biplane, factor);
  417.                 break;
  418.             case STYPE_SPHERE:
  419.                 if ( !sphere_to_quad(shape) )
  420.                     return FALSE;
  421.                 scale_y_quad(shape->u.quad, factor);
  422.                 break;
  423.             case STYPE_QUAD:
  424.                 scale_y_quad(shape->u.quad, factor);
  425.                 break;
  426.             }
  427.         scale_y_surf(shape->surf, factor);
  428.         }
  429.     else
  430.         {
  431.         if ( !scale_y(shape->u.shapes[0], factor) ||
  432.              !scale_y(shape->u.shapes[1], factor) )
  433.             return FALSE;
  434.         }
  435.     return TRUE;
  436.     }
  437. /*...e*/
  438. /*...sscale_z              \45\ scale by factor in z direction:0:*/
  439. BOOLEAN    scale_z(SHAPE *shape, double factor)
  440.     {
  441.     if ( factor == 1.0 )
  442.         return TRUE;
  443.  
  444.     if ( shape->stype <= STYPE_QUAD )
  445.         {
  446.         switch ( shape->stype )
  447.             {
  448.             case STYPE_PLANE:
  449.                 scale_z_plane(shape->u.plane, factor);
  450.                 break;
  451.             case STYPE_BIPLANE:
  452.                 scale_z_biplane(shape->u.biplane, factor);
  453.                 break;
  454.             case STYPE_SPHERE:
  455.                 if ( !sphere_to_quad(shape) )
  456.                     return FALSE;
  457.                 scale_z_quad(shape->u.quad, factor);
  458.                 break;
  459.             case STYPE_QUAD:
  460.                 scale_z_quad(shape->u.quad, factor);
  461.                 break;
  462.             }
  463.         scale_z_surf(shape->surf, factor);
  464.         }
  465.     else
  466.         {
  467.         if ( !scale_z(shape->u.shapes[0], factor) ||
  468.              !scale_z(shape->u.shapes[1], factor) )
  469.             return FALSE;
  470.         }
  471.     return TRUE;
  472.     }
  473. /*...e*/
  474. /*...sscale                \45\ scale by vector factor:0:*/
  475. BOOLEAN    scale(SHAPE *shape, VECTOR factor)
  476.     {
  477.     if ( shape->stype == STYPE_SPHERE &&
  478.          factor.x == factor.y && factor.y == factor.z )
  479.         {
  480.         scale_sphere(shape->u.sphere, factor.x);
  481.         scale_x_surf(shape->surf, factor.x);
  482.         scale_y_surf(shape->surf, factor.y);
  483.         scale_z_surf(shape->surf, factor.z);
  484.         }
  485.     else
  486.         {
  487.         if ( !scale_x(shape, factor.x) ||
  488.              !scale_y(shape, factor.y) ||
  489.              !scale_z(shape, factor.z) )
  490.             return FALSE;
  491.         }
  492.     return TRUE;
  493.     }
  494. /*...e*/
  495. /*...srot_x                \45\ rotate about x axis by given angle:0:*/
  496. void    rot_x(SHAPE *shape, double angle)
  497.     {
  498.     if ( shape->stype <= STYPE_QUAD )
  499.         {
  500.         switch ( shape->stype )
  501.             {
  502.             case STYPE_PLANE:
  503.                 rot_x_plane(shape->u.plane, angle);
  504.                 break;
  505.             case STYPE_BIPLANE:
  506.                 rot_x_biplane(shape->u.biplane, angle);
  507.                 break;
  508.             case STYPE_SPHERE:
  509.                 rot_x_sphere(shape->u.sphere, angle);
  510.                 break;
  511.             case STYPE_QUAD:
  512.                 rot_x_quad(shape->u.quad, angle);
  513.                 break;
  514.             }
  515.         rot_x_surf(shape->surf, angle);
  516.         }
  517.     else
  518.         {
  519.         rot_x(shape->u.shapes[0], angle);
  520.         rot_x(shape->u.shapes[1], angle);
  521.         }
  522.     }
  523. /*...e*/
  524. /*...srot_y                \45\ rotate about y axis by given angle:0:*/
  525. void    rot_y(SHAPE *shape, double angle)
  526.     {
  527.     if ( shape->stype <= STYPE_QUAD )
  528.         {
  529.         switch ( shape->stype )
  530.             {
  531.             case STYPE_PLANE:
  532.                 rot_y_plane(shape->u.plane, angle);
  533.                 break;
  534.             case STYPE_BIPLANE:
  535.                 rot_y_biplane(shape->u.biplane, angle);
  536.                 break;
  537.             case STYPE_SPHERE:
  538.                 rot_y_sphere(shape->u.sphere, angle);
  539.                 break;
  540.             case STYPE_QUAD:
  541.                 rot_y_quad(shape->u.quad, angle);
  542.                 break;
  543.             }
  544.         rot_y_surf(shape->surf, angle);
  545.         }
  546.     else
  547.         {
  548.         rot_y(shape->u.shapes[0], angle);
  549.         rot_y(shape->u.shapes[1], angle);
  550.         }
  551.     }
  552. /*...e*/
  553. /*...srot_z                \45\ rotate about z axis by given angle:0:*/
  554. void    rot_z(SHAPE *shape, double angle)
  555.     {
  556.     if ( shape->stype <= STYPE_QUAD )
  557.         {
  558.         switch ( shape->stype )
  559.             {
  560.             case STYPE_PLANE:
  561.                 rot_z_plane(shape->u.plane, angle);
  562.                 break;
  563.             case STYPE_BIPLANE:
  564.                 rot_z_biplane(shape->u.biplane, angle);
  565.                 break;
  566.             case STYPE_SPHERE:
  567.                 rot_z_sphere(shape->u.sphere, angle);
  568.                 break;
  569.             case STYPE_QUAD:
  570.                 rot_z_quad(shape->u.quad, angle);
  571.                 break;
  572.             }
  573.         rot_z_surf(shape->surf, angle);
  574.         }
  575.     else
  576.         {
  577.         rot_z(shape->u.shapes[0], angle);
  578.         rot_z(shape->u.shapes[1], angle);
  579.         }
  580.     }
  581. /*...e*/
  582.  
  583. /*...sresurf               \45\ change the surface of a shape:0:*/
  584. BOOLEAN resurf(SHAPE *shape, SURF *surf)
  585.     {
  586.     if ( shape->stype <= STYPE_QUAD )
  587.         {
  588.         SURF *surf_copy;
  589.  
  590.         if ( (surf_copy = copy_surf(surf)) == NULL )
  591.             return FALSE;
  592.  
  593.         destroy_surf(shape->surf);
  594.         shape->surf = surf_copy;
  595.         }
  596.     else
  597.         {
  598.         if ( !resurf(shape->u.shapes[0], surf) )
  599.             return FALSE;
  600.         if ( !resurf(shape->u.shapes[1], surf) )
  601.             return FALSE;
  602.         }
  603.  
  604.     return TRUE;
  605.     }
  606. /*...e*/
  607.  
  608. /*...sis_empty_isectl      \45\ is intersection list empty:0:*/
  609. BOOLEAN    is_empty_isectl(ISECTL *il)
  610.     {
  611.     return il->n_isects == 0;
  612.     }
  613. /*...e*/
  614. /*...sis_solid_isectl      \45\ is intersection list solid:0:*/
  615. /*
  616. We will allow t from -INFINITE onwards or t from -INFINITE to INFINITE.
  617. */
  618.  
  619. BOOLEAN    is_solid_isectl(ISECTL *il)
  620.     {
  621.     if ( il->n_isects > 2 )
  622.         return FALSE;
  623.  
  624.     if ( il->isects[0].t != -INFINITE )
  625.         return FALSE;
  626.  
  627.     return il->n_isects == 1 || il->isects[1].t == INFINITE;
  628.     }
  629. /*...e*/
  630. /*...st_after_isectl       \45\ eliminate all intersections before a t value:0:*/
  631. void    t_after_isectl(ISECTL *il, double t)
  632.     {
  633.     int    i;
  634.  
  635.     for ( i = 0; i < il->n_isects; i++ )
  636.         if ( il->isects[i].t >= t )
  637.             break;
  638.  
  639.     if ( i == il->n_isects )
  640.         /* All behind t */
  641.         il->n_isects = 0;
  642.     else if ( i != 0 )
  643.         /* Some behind and some after t */
  644.         {
  645.         int    j = 0;
  646.  
  647.         if ( il->isects[i].entering == FALSE )
  648.             /* Had better make an isect case first */
  649.             {
  650.             il->isects[j  ]   = il->isects[i - 1];
  651.             il->isects[j++].t = t;
  652.             }
  653.  
  654.         while ( i < il->n_isects )
  655.             il->isects[j++] = il->isects[i++];
  656.         il->n_isects = j;
  657.         }
  658.     }
  659. /*...e*/
  660.  
  661. /*...screate_isectl        \45\ create an isectl:0:*/
  662. ISECTL    *create_isectl(int n_isects)
  663.     {
  664.     return malloc(sizeof(ISECTL) + (n_isects - 1) * sizeof(ISECT));
  665.     }
  666. /*...e*/
  667. /*...sdestroy_isectl       \45\ destroy an isectl:0:*/
  668. void    destroy_isectl(ISECTL *il)
  669.     {
  670.     free(il);
  671.     }
  672. /*...e*/
  673.  
  674. /*...spreprocess_shape     \45\ preprocess shape tree to save work when tracing:0:*/
  675. /*...sextent_shape:0:*/
  676. /*
  677. If we can find shapes that do not overlap, we can avoid tracing time later.
  678. This type of function is only made possible because the code that implements
  679. spheres etc. export their internal representations of the shapes.
  680. */
  681.  
  682. /*...sspheres_overlap:0:*/
  683. /*
  684. 2 spheres overlap if the sum of the radii > distance between the centres.
  685. We square both sides of this equation.
  686. */
  687.  
  688. static BOOLEAN spheres_overlap(SPHERE *sphere_a, SPHERE *sphere_b)
  689.     {
  690.     double    dx = sphere_a->a - sphere_b->a;
  691.     double    dy = sphere_a->b - sphere_b->b;
  692.     double    dz = sphere_a->c - sphere_b->c;
  693.     double    rr = sphere_a->d + sphere_b->d;
  694.  
  695.     return rr*rr >= dx*dx + dy*dy + dz*dz;
  696.     }
  697. /*...e*/
  698.  
  699. typedef struct { VECTOR xmin, xmax; } EXTENT;
  700.  
  701. /*...sextent_infinite:0:*/
  702. static EXTENT extent_infinite(void)
  703.     {
  704.     EXTENT    extent;
  705.  
  706.     extent.xmin.x = extent.xmin.y = extent.xmin.z = -INFINITE;
  707.     extent.xmax.x = extent.xmax.y = extent.xmax.z =  INFINITE;
  708.     return extent;
  709.     }
  710. /*...e*/
  711. /*...sextent_of_plane:0:*/
  712. /*
  713.  
  714. ax+by+cz+d<= 0
  715.  
  716. Quite a lot of models have their plane faces aligned along x,y y,z or x,z
  717. planes. Hence this code should discover that fact quite often.
  718.  
  719. */
  720.  
  721. static EXTENT extent_of_plane(PLANE *plane)
  722.     {
  723.     double    a = plane->a;
  724.     double    b = plane->b;
  725.     double    c = plane->c;
  726.     double    d = plane->d;
  727.     EXTENT    extent = extent_infinite();
  728.  
  729.     if ( b == 0.0 && c == 0.0 )
  730.         /* ax<=-d */
  731.         {
  732.         if ( a >= 0.0 )
  733.             extent.xmax.x = -d/a;
  734.         else
  735.             extent.xmin.x = -d/a;
  736.         }
  737.     else if ( a == 0.0 && c == 0.00 )
  738.         /* by<=-d */
  739.         {
  740.         if ( b >= 0.0 )
  741.             extent.xmax.y = -d/b;
  742.         else
  743.             extent.xmin.y = -d/b;
  744.         }
  745.     else if ( a == 0.0 && b == 0.0 )
  746.         /* cz<=-d */
  747.         {
  748.         if ( c >= 0.0 )
  749.             extent.xmax.z = -d/c;
  750.         else
  751.             extent.xmin.z = -d/c;
  752.         }
  753.  
  754.     return extent;
  755.     }
  756. /*...e*/
  757. /*...sextent_of_biplane:0:*/
  758. /*
  759.  
  760. ax+by+cz+d1 >  0 and
  761. ax+by+cz+d2 <= 0
  762.  
  763. Quite a lot of models have their plane faces aligned along x,y y,z or x,z
  764. planes. Hence this code should discover that fact quite often.
  765.  
  766. */
  767.  
  768. static EXTENT extent_of_biplane(BIPLANE *biplane)
  769.     {
  770.     double    a  = biplane->a;
  771.     double    b  = biplane->b;
  772.     double    c  = biplane->c;
  773.     double    d1 = biplane->d1;
  774.     double    d2 = biplane->d2;
  775.     EXTENT    extent = extent_infinite();
  776.  
  777.     if ( b == 0.0 && c == 0.0 )
  778.         /* ax>-d1 and ax<=-d2 */
  779.         {
  780.         if ( a >= 0.0 )
  781.             {
  782.             extent.xmin.x = -d1/a;
  783.             extent.xmax.x = -d2/a;
  784.             }
  785.         else
  786.             {
  787.             extent.xmin.x = -d2/a;
  788.             extent.xmax.x = -d1/a;
  789.             }
  790.         }
  791.     else if ( a == 0.0 && c == 0.00 )
  792.         /* by>-d1 and by<=-d2 */
  793.         {
  794.         if ( b >= 0.0 )
  795.             {
  796.             extent.xmin.y = -d1/b;
  797.             extent.xmax.y = -d2/b;
  798.             }
  799.         else
  800.             {
  801.             extent.xmin.y = -d2/b;
  802.             extent.xmax.y = -d1/b;
  803.             }
  804.         }
  805.     else if ( a == 0.0 && b == 0.0 )
  806.         /* cz>-d1 and cz<=-d2 */
  807.         {
  808.         if ( c >= 0.0 )
  809.             {
  810.             extent.xmin.z = -d1/c;
  811.             extent.xmax.z = -d2/c;
  812.             }
  813.         else
  814.             {
  815.             extent.xmin.z = -d2/c;
  816.             extent.xmax.z = -d1/c;
  817.             }
  818.         }
  819.  
  820.     return extent;
  821.     }
  822. /*...e*/
  823. /*...sextent_of_sphere:0:*/
  824. static EXTENT extent_of_sphere(SPHERE *sphere)
  825.     {
  826.     double    a = sphere->a;
  827.     double    b = sphere->b;
  828.     double    c = sphere->c;
  829.     double    d = sphere->d;
  830.     EXTENT    extent;
  831.  
  832.     extent.xmin.x = a - d; extent.xmax.x = a + d;
  833.     extent.xmin.y = b - d; extent.xmax.y = b + d;
  834.     extent.xmin.z = c - d; extent.xmax.z = c + d;
  835.  
  836.     return extent;
  837.     }
  838. /*...e*/
  839. /*...sextents_overlap:0:*/
  840. static BOOLEAN extents_overlap(EXTENT *extent_a, EXTENT *extent_b)
  841.     {
  842.     return extent_a->xmax.x > extent_b->xmin.x &&
  843.            extent_a->xmax.y > extent_b->xmin.y &&
  844.            extent_a->xmax.z > extent_b->xmin.z &&
  845.            extent_b->xmax.x > extent_a->xmin.x &&
  846.            extent_b->xmax.y > extent_a->xmin.y &&
  847.            extent_b->xmax.z > extent_a->xmin.z ;
  848.     }
  849. /*...e*/
  850. /*...sextents_union:0:*/
  851. static EXTENT extents_union(EXTENT *extent_a, EXTENT *extent_b)
  852.     {
  853.     EXTENT extent;
  854.  
  855.     extent.xmin.x = min(extent_a->xmin.x, extent_b->xmin.x);
  856.     extent.xmin.y = min(extent_a->xmin.y, extent_b->xmin.y);
  857.     extent.xmin.z = min(extent_a->xmin.z, extent_b->xmin.z);
  858.     extent.xmax.x = max(extent_a->xmax.x, extent_b->xmax.x);
  859.     extent.xmax.y = max(extent_a->xmax.y, extent_b->xmax.y);
  860.     extent.xmax.z = max(extent_a->xmax.z, extent_b->xmax.z);
  861.  
  862.     return extent;
  863.     }
  864. /*...e*/
  865. /*...sextents_isect:0:*/
  866. static EXTENT extents_isect(EXTENT *extent_a, EXTENT *extent_b)
  867.     {
  868.     EXTENT    extent;
  869.  
  870.     extent.xmin.x = max(extent_a->xmin.x, extent_b->xmin.x);
  871.     extent.xmin.y = max(extent_a->xmin.y, extent_b->xmin.y);
  872.     extent.xmin.z = max(extent_a->xmin.z, extent_b->xmin.z);
  873.     extent.xmax.x = min(extent_a->xmax.x, extent_b->xmax.x);
  874.     extent.xmax.y = min(extent_a->xmax.y, extent_b->xmax.y);
  875.     extent.xmax.z = min(extent_a->xmax.z, extent_b->xmax.z);
  876.  
  877.     return extent;
  878.     }
  879. /*...e*/
  880.  
  881. static EXTENT extent_shape(SHAPE *shape)
  882.     {
  883.     static EXTENT dummy_extent = { { 0.0, 0.0, 0.0 }, { 0.0, 0.0, 0.0 } };
  884.  
  885.     if ( shape->stype <= STYPE_QUAD )
  886.         {
  887.         switch ( shape->stype )
  888.             {
  889. /*...sSTYPE_PLANE:24:*/
  890. case STYPE_PLANE:
  891.     return extent_of_plane(shape->u.plane);
  892. /*...e*/
  893. /*...sSTYPE_BIPLANE:24:*/
  894. case STYPE_BIPLANE:
  895.     return extent_of_biplane(shape->u.biplane);
  896. /*...e*/
  897. /*...sSTYPE_QUAD \45\ too difficult:24:*/
  898. case STYPE_QUAD:
  899.     return extent_infinite();
  900. /*...e*/
  901. /*...sSTYPE_SPHERE:24:*/
  902. case STYPE_SPHERE:
  903.     return extent_of_sphere(shape->u.sphere);
  904. /*...e*/
  905.             }
  906.         }
  907.     else if ( shape->stype == STYPE_EXTENT )
  908.         {
  909.         EXTENT extent;
  910.  
  911.         extent = extent_shape(shape->u.shapes[0]);
  912.         /* Performed for side effect of extent_shape() call */
  913.  
  914.         return extent_shape(shape->u.shapes[1]);
  915.         }
  916.     else
  917.         {
  918.         SHAPE    *shape_a = shape->u.shapes[0];
  919.         SHAPE    *shape_b = shape->u.shapes[1];
  920.         EXTENT    extent_a = extent_shape(shape_a);
  921.         EXTENT    extent_b = extent_shape(shape_b);
  922.         EXTENT    extent;
  923.  
  924.         switch ( shape->stype )
  925.             {
  926. /*...sSTYPE_UNION\44\ STYPE_SDIFF:24:*/
  927. case STYPE_UNION:
  928. case STYPE_SDIFF:
  929.     extent = extents_union(&extent_a, &extent_b);
  930.     break;
  931. /*...e*/
  932. /*...sSTYPE_ISECT:24:*/
  933. case STYPE_ISECT:
  934.     extent = extents_isect(&extent_a, &extent_b);
  935.     break;
  936. /*...e*/
  937. /*...sSTYPE_DIFF:24:*/
  938. case STYPE_DIFF:
  939.     extent = extent_a;
  940.     break;
  941. /*...e*/
  942.             }
  943.  
  944.         if ( shape_a->stype == STYPE_SPHERE &&
  945.              shape_b->stype == STYPE_SPHERE )
  946.             shape->overlap = spheres_overlap(
  947.                 shape_a->u.sphere, shape_b->u.sphere);
  948.         else
  949.             shape->overlap = extents_overlap(&extent_a, &extent_b);
  950.  
  951.         return extent;
  952.         }
  953.  
  954.     return dummy_extent; /* Keep fussy C compiler happy */
  955.     }
  956. /*...e*/
  957. /*...sn_isectls_reqd_shape:0:*/
  958. /*
  959. We use this function so that we can work out how many intersection lists
  960. we will need to pre-allocate for tracing the shape.
  961. */
  962.  
  963. int    n_isectls_reqd_shape(SHAPE *shape)
  964.     {
  965.     int nest0, nest1;
  966.  
  967.     if ( shape->stype <= STYPE_QUAD )
  968.         return 1;
  969.  
  970.     nest0 = n_isectls_reqd_shape(shape->u.shapes[0]);
  971.     nest1 = n_isectls_reqd_shape(shape->u.shapes[1]);
  972.  
  973.     return 2 + max(nest0, nest1);
  974.     }
  975. /*...e*/
  976. /*...sisects_reqd_shape:0:*/
  977. /*
  978. Determine largest needed intersection list.
  979. */
  980.  
  981. int    isects_reqd_shape(SHAPE *shape)
  982.     {
  983.     if ( shape->stype <= STYPE_QUAD )
  984.         switch ( shape->stype )
  985.             {
  986. /*...sSTYPE_PLANE:24:*/
  987. case STYPE_PLANE:
  988.     return isects_reqd_plane(shape->u.plane);
  989. /*...e*/
  990. /*...sSTYPE_BIPLANE:24:*/
  991. case STYPE_BIPLANE:
  992.     return isects_reqd_biplane(shape->u.biplane);
  993. /*...e*/
  994. /*...sSTYPE_SPHERE:24:*/
  995. case STYPE_SPHERE:
  996.     return isects_reqd_sphere(shape->u.sphere);
  997. /*...e*/
  998. /*...sSTYPE_QUAD:24:*/
  999. case STYPE_QUAD:
  1000.     return isects_reqd_quad(shape->u.quad);
  1001. /*...e*/
  1002.             }
  1003.     else
  1004.         {
  1005.         int    reqd0 = isects_reqd_shape(shape->u.shapes[0]);
  1006.         int    reqd1 = isects_reqd_shape(shape->u.shapes[1]);
  1007.  
  1008.         switch ( shape->stype )
  1009.             {
  1010. /*...sSTYPE_UNION:24:*/
  1011. case STYPE_UNION:
  1012.     return reqd0 + reqd1;
  1013. /*...e*/
  1014. /*...sSTYPE_ISECT:24:*/
  1015. case STYPE_ISECT:
  1016.     return ( shape->overlap ) ? reqd0 + reqd1 : 0;
  1017. /*...e*/
  1018. /*...sSTYPE_DIFF:24:*/
  1019. case STYPE_DIFF:
  1020.     return ( shape->overlap ) ? reqd0 + reqd1 : reqd0;
  1021. /*...e*/
  1022. /*...sSTYPE_SDIFF:24:*/
  1023. case STYPE_SDIFF:
  1024.     return reqd0 + reqd1;
  1025. /*...e*/
  1026. /*...sSTYPE_EXTENT:24:*/
  1027. case STYPE_EXTENT:
  1028.     return max(reqd0, reqd1);
  1029. /*...e*/
  1030.             }
  1031.         }
  1032.     return 0; /* Keep fussy C compiler happy */
  1033.     }
  1034. /*...e*/
  1035.  
  1036. void    preprocess_shape(SHAPE *shape, int *n_isectls, int *n_isects)
  1037.     {
  1038.     EXTENT    extent;
  1039.  
  1040.     extent = extent_shape(shape);
  1041.         /* The side effect is to label the shape tree */
  1042.  
  1043.     *n_isectls = n_isectls_reqd_shape(shape);
  1044.     *n_isects  = isects_reqd_shape(shape);
  1045.     }
  1046. /*...e*/
  1047. /*...sintersect_shape      \45\ intersect with a shape to give a ISECTL:0:*/
  1048. /*
  1049. Given a shape tree, find the intersection list of a vector with it.
  1050. If the shape tree is not a leaf node, then combine the intersection lists of
  1051. the subtrees. We can make several optimisations in this area.
  1052. */
  1053.  
  1054. /*...smake_empty_isectl:0:*/
  1055. static void make_empty_isectl(ISECTL *il)
  1056.     {
  1057.     il->n_isects = 0;
  1058.     }
  1059. /*...e*/
  1060. /*...scopy_isectl:0:*/
  1061. static void copy_isectl(ISECTL *il_dst, ISECTL *il_src)
  1062.     {
  1063.     int    i;
  1064.  
  1065.     il_dst->n_isects = il_src->n_isects;
  1066.     for ( i = 0; i < il_dst->n_isects; i++ )
  1067.         il_dst->isects[i] = il_src->isects[i];
  1068.     }
  1069. /*...e*/
  1070. /*...scombine_isectl:0:*/
  1071. /*
  1072. Given 2 intersection lists, produce a new one that is a combination of them.
  1073.  
  1074. The in_old flag is used to determine if the point of intersection changes
  1075. meaning from in->out to out->in, or vice-versa. If this happens, the
  1076. sense of the normal vector must change :-
  1077.  
  1078.          ..... .....                .....
  1079.         .     .     .              .     .
  1080.        .  A  . .  B  .            . A-B .
  1081.       .     .   .     .          .     .
  1082.     <-.   <-.   .->   .->      <-.     .-> This vector changes direction!
  1083.       .     .   .     .          .     .
  1084.        .     . .     .            .     .
  1085.         .     .     .              .     .
  1086.          ..... .....                .....
  1087.  
  1088. */
  1089.  
  1090. static void combine_isectl(
  1091.     BOOLEAN (*combine)(BOOLEAN in_a, BOOLEAN in_b),
  1092.     ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1093.     {
  1094.     BOOLEAN    in_a = FALSE;    /* When t = -INFINITE, in_a = FALSE */
  1095.     BOOLEAN    in_b = FALSE;    /* When t = -INFINITE, in_b = FALSE */
  1096.     BOOLEAN    in = FALSE;    /* Therefore combination starts as FALSE */
  1097.     int    ptr_a = 0;
  1098.     int    ptr_b = 0;
  1099.     BOOLEAN    in_new, in_old;
  1100.  
  1101.     il->n_isects = 0;
  1102.  
  1103.     /* Work through both a and b, looking at nearest ones first */
  1104.  
  1105.     while ( ptr_a < il_a->n_isects && ptr_b < il_b->n_isects )
  1106.         {
  1107.         ISECT    *isect;
  1108.         double    t_a = il_a->isects[ptr_a].t;
  1109.         double    t_b = il_b->isects[ptr_b].t;
  1110.  
  1111.         if ( t_a < t_b )
  1112.             {
  1113.             in_old = in_a = !in_a;
  1114.             isect = &(il_a->isects[ptr_a++]);
  1115.             }
  1116.         else if ( t_a > t_b )
  1117.             {
  1118.             in_old = in_b = !in_b;
  1119.             isect = &(il_b->isects[ptr_b++]);
  1120.             }
  1121.         else
  1122.             /* Two surfaces at exactly the same place */
  1123.             /* Not a very frequent event, but problematical */
  1124.             /* Just label intersection arbitrarily as with B */
  1125.             {
  1126.             in_a = !in_a; ptr_a++;
  1127.             in_old = in_b = !in_b;
  1128.             isect = &(il_b->isects[ptr_b++]);
  1129.             }
  1130.  
  1131.         if ( (in_new = (*combine)(in_a, in_b)) != in )
  1132.             /* Need to keep a record of this transition */
  1133.             {
  1134.             il->isects[il->n_isects] = *isect;
  1135.             il->isects[il->n_isects].entering = in = in_new;
  1136.             if ( in_new != in_old )
  1137.                 il->isects[il->n_isects].negate_normal ^= TRUE;
  1138.             il->n_isects++;
  1139.             }
  1140.         }
  1141.  
  1142.     /* Either a or b is exhausted, so one of a or b may be left */
  1143.  
  1144.     while ( ptr_a < il_a->n_isects )
  1145.         {
  1146.         in_old = in_a = !in_a;
  1147.         if ( (in_new = (*combine)(in_a, in_b)) != in )
  1148.             /* Need to keep a record of this transition */
  1149.             {
  1150.             il->isects[il->n_isects] = il_a->isects[ptr_a];
  1151.             il->isects[il->n_isects].entering = in = in_new;
  1152.             if ( in_new != in_old )
  1153.                 il->isects[il->n_isects].negate_normal ^= TRUE;
  1154.             il->n_isects++;
  1155.             }
  1156.         ptr_a++;
  1157.         }
  1158.  
  1159.     while ( ptr_b < il_b->n_isects )
  1160.         {
  1161.         in_old = in_b = !in_b;
  1162.         if ( (in_new = (*combine)(in_a, in_b)) != in )
  1163.             /* Need to keep a record of this transition */
  1164.             {
  1165.             il->isects[il->n_isects] = il_b->isects[ptr_b];
  1166.             il->isects[il->n_isects].entering = in = in_new;
  1167.             if ( in_new != in_old )
  1168.                 il->isects[il->n_isects].negate_normal ^= TRUE;
  1169.             il->n_isects++;
  1170.             }
  1171.         ptr_b++;
  1172.         }
  1173.     }
  1174. /*...e*/
  1175. /*...sunion_isectl:0:*/
  1176. /*...scombine_union:0:*/
  1177. static BOOLEAN combine_union(BOOLEAN in_a, BOOLEAN in_b)
  1178.     {
  1179.     return in_a || in_b;
  1180.     }
  1181. /*...e*/
  1182.  
  1183. static void union_isectl(ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1184.     {
  1185.     combine_isectl(combine_union, il_a, il_b, il);
  1186.     }
  1187. /*...e*/
  1188. /*...sisect_isectl:0:*/
  1189. /*...scombine_isect:0:*/
  1190. static BOOLEAN combine_isect(BOOLEAN in_a, BOOLEAN in_b)
  1191.     {
  1192.     return in_a && in_b;
  1193.     }
  1194. /*...e*/
  1195.  
  1196. static void isect_isectl(ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1197.     {
  1198.     combine_isectl(combine_isect, il_a, il_b, il);
  1199.     }
  1200. /*...e*/
  1201. /*...sdiff_isectl:0:*/
  1202. /*...scombine_diff:0:*/
  1203. static BOOLEAN combine_diff(BOOLEAN in_a, BOOLEAN in_b)
  1204.     {
  1205.     return in_a && !in_b;
  1206.     }
  1207. /*...e*/
  1208.  
  1209. static void diff_isectl(ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1210.     {
  1211.     combine_isectl(combine_diff, il_a, il_b, il);
  1212.     }
  1213. /*...e*/
  1214. /*...ssdiff_isectl:0:*/
  1215. /*...scombine_sdiff:0:*/
  1216. static BOOLEAN combine_sdiff(BOOLEAN in_a, BOOLEAN in_b)
  1217.     {
  1218.     return in_a ^ in_b;
  1219.     }
  1220. /*...e*/
  1221.  
  1222. static void sdiff_isectl(ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1223.     {
  1224.     combine_isectl(combine_sdiff, il_a, il_b, il);
  1225.     }
  1226. /*...e*/
  1227. /*...sconcat_isectl:0:*/
  1228. /*
  1229. This is a quick case of unioning two intersection lists for use when it is
  1230. known that they do not overlap.
  1231. */
  1232.  
  1233. static void concat_isectl(ISECTL *il_a, ISECTL *il_b, ISECTL *il)
  1234.     {
  1235.     ISECTL    *il_rest;
  1236.     int    i, j;
  1237.  
  1238.     if ( il_a->n_isects == 0 )
  1239.         {
  1240.         copy_isectl(il, il_b);
  1241.         return;
  1242.         }
  1243.  
  1244.     if ( il_b->n_isects == 0 )
  1245.         {
  1246.         copy_isectl(il, il_a);
  1247.         return;
  1248.         }
  1249.  
  1250.     if ( il_a->isects[0].t < il_b->isects[0].t )
  1251.         {
  1252.         copy_isectl(il, il_a);
  1253.         il_rest = il_b;
  1254.         }
  1255.     else
  1256.         {
  1257.         copy_isectl(il, il_b);
  1258.         il_rest = il_a;
  1259.         }
  1260.  
  1261.     for ( i = 0, j = il->n_isects; i < il_rest->n_isects; i++, j++ )
  1262.         il->isects[j] = il_rest->isects[i];
  1263.  
  1264.     il->n_isects = j;
  1265.     }
  1266. /*...e*/
  1267.  
  1268. void    intersect_shape(SHAPE *shape, VECTOR p, VECTOR q, ISECTL *ils[])
  1269.     {
  1270.     if ( shape->stype <= STYPE_QUAD )
  1271.         /* Is a leaf node */
  1272.         {
  1273.         SIL    sil;
  1274.         int    i;
  1275.     
  1276.         switch ( shape->stype )
  1277.             {
  1278. /*...sSTYPE_PLANE:24:*/
  1279. case STYPE_PLANE:
  1280.     intersect_plane(shape->u.plane, p, q, &sil);
  1281.     break;
  1282. /*...e*/
  1283. /*...sSTYPE_BIPLANE:24:*/
  1284. case STYPE_BIPLANE:
  1285.     intersect_biplane(shape->u.biplane, p, q, &sil);
  1286.     break;
  1287. /*...e*/
  1288. /*...sSTYPE_SPHERE:24:*/
  1289. case STYPE_SPHERE:
  1290.     intersect_sphere(shape->u.sphere, p, q, &sil);
  1291.     break;
  1292. /*...e*/
  1293. /*...sSTYPE_QUAD:24:*/
  1294. case STYPE_QUAD:
  1295.     intersect_quad(shape->u.quad, p, q, &sil);
  1296.     break;
  1297. /*...e*/
  1298.             }
  1299.         ils[0]->n_isects = sil.n_sis;
  1300.         for ( i = 0; i < sil.n_sis; i++ )
  1301.             {
  1302.             ils[0]->isects[i].t             = sil.sis[i].t;
  1303.             ils[0]->isects[i].entering      = sil.sis[i].entering;
  1304.             ils[0]->isects[i].shape         = shape;
  1305.             ils[0]->isects[i].negate_normal = FALSE;
  1306.             }
  1307.         }
  1308.     else
  1309.         /* Binary combination of two subtrees */
  1310.         {
  1311.         SHAPE    *shape_a = shape->u.shapes[0];
  1312.         SHAPE    *shape_b = shape->u.shapes[1];
  1313.  
  1314.         switch ( shape->stype )
  1315.             {
  1316. /*...sSTYPE_UNION:24:*/
  1317. case STYPE_UNION:
  1318.     if ( shape->overlap )
  1319.         {
  1320.         intersect_shape(shape_b, p, q, ils + 1);
  1321.         if ( is_empty_isectl(ils[1]) )
  1322.             intersect_shape(shape_a, p, q, ils);
  1323.         else if ( is_solid_isectl(ils[1]) )
  1324.             copy_isectl(ils[0], ils[1]);
  1325.         else
  1326.             {
  1327.             intersect_shape(shape_a, p, q, ils + 2);
  1328.             union_isectl(ils[2], ils[1], ils[0]);
  1329.             }
  1330.         }
  1331.     else
  1332.         /* No overlap, treat like concatentation */
  1333.         {
  1334.         intersect_shape(shape_a, p, q, ils + 1);
  1335.         intersect_shape(shape_b, p, q, ils + 2);
  1336.         concat_isectl(ils[1], ils[2], ils[0]);
  1337.         }
  1338.     break;
  1339. /*...e*/
  1340. /*...sSTYPE_ISECT:24:*/
  1341. case STYPE_ISECT:
  1342.     if ( shape->overlap )
  1343.         {
  1344.         intersect_shape(shape_b, p, q, ils + 1);
  1345.         if ( is_empty_isectl(ils[1]) )
  1346.             make_empty_isectl(ils[0]);
  1347.         else if ( is_solid_isectl(ils[1]) )
  1348.             intersect_shape(shape_a, p, q, ils);
  1349.         else
  1350.             {
  1351.             intersect_shape(shape_a, p, q, ils + 2);
  1352.             isect_isectl(ils[2], ils[1], ils[0]);
  1353.             }
  1354.         }
  1355.     else
  1356.         make_empty_isectl(ils[0]);
  1357.     break;
  1358. /*...e*/
  1359. /*...sSTYPE_DIFF:24:*/
  1360. case STYPE_DIFF:
  1361.     if ( shape->overlap )
  1362.         {
  1363.         intersect_shape(shape_b, p, q, ils + 1);
  1364.         if ( is_empty_isectl(ils[1]) )
  1365.             intersect_shape(shape_a, p, q, ils);
  1366.         else if ( is_solid_isectl(ils[1]) )
  1367.             make_empty_isectl(ils[0]);
  1368.         else
  1369.             {
  1370.             intersect_shape(shape_a, p, q, ils + 2);
  1371.             diff_isectl(ils[2], ils[1], ils[0]);
  1372.             }
  1373.         }
  1374.     else
  1375.         intersect_shape(shape_a, p, q, ils);
  1376.     break;
  1377. /*...e*/
  1378. /*...sSTYPE_SDIFF:24:*/
  1379. case STYPE_SDIFF:
  1380.     if ( shape->overlap )
  1381.         {
  1382.         intersect_shape(shape_b, p, q, ils + 1);
  1383.         if ( is_empty_isectl(ils[1]) )
  1384.             intersect_shape(shape_a, p, q, ils);
  1385.         else
  1386.             {
  1387.             intersect_shape(shape_a, p, q, ils + 2);
  1388.             sdiff_isectl(ils[2], ils[1], ils[0]);
  1389.             }
  1390.         }
  1391.     else
  1392.         /* No overlap, treat like concatentation */
  1393.         {
  1394.         intersect_shape(shape_a, p, q, ils + 1);
  1395.         intersect_shape(shape_b, p, q, ils + 2);
  1396.         concat_isectl(ils[1], ils[2], ils[0]);
  1397.         }
  1398.     break;
  1399. /*...e*/
  1400. /*...sSTYPE_EXTENT:24:*/
  1401. case STYPE_EXTENT:
  1402.     intersect_shape(shape_b, p, q, ils);
  1403.     if ( !is_empty_isectl(ils[0]) )
  1404.         intersect_shape(shape_a, p, q, ils);
  1405.     break;
  1406. /*...e*/
  1407.             }
  1408.         }
  1409.     }
  1410. /*...e*/
  1411. /*...snormal_to_shape      \45\ find normal at point on edge of shape:0:*/
  1412. VECTOR    normal_to_shape(SHAPE *shape, VECTOR p)
  1413.     {
  1414.     static VECTOR dummy_vector = { 0.0, 0.0, 0.0 };
  1415.  
  1416.     switch ( shape->stype )
  1417.         {
  1418.         case STYPE_PLANE:
  1419.             return normal_to_plane(shape->u.plane);
  1420.         case STYPE_BIPLANE:
  1421.             return normal_to_biplane(shape->u.biplane, p);
  1422.         case STYPE_SPHERE:
  1423.             return normal_to_sphere(shape->u.sphere, p);
  1424.         case STYPE_QUAD:
  1425.             return normal_to_quad(shape->u.quad, p);
  1426.         }
  1427.     return dummy_vector; /* Keep fussy C compiler happy */
  1428.     }
  1429. /*...e*/
  1430.